解決陣列在動態資料操作上的基本限制。

  • 陣列耗時 $O(n)$ 的修改時間所帶來的關鍵教訓是：物理連續性是問題的根本原因，迫使我們在位置 $i$ 插入或刪除元素時必須移動其他元素。
  • 若應用程式需要頻繁且快速的修改（插入或刪除），即使陣列具有 $O(1)$ 的隨機存取能力，其效率仍然不佳。
  • 為達成最佳的$O(1)$ 修改複雜度，我們必須找到一種根本改變元素儲存與排序方式的順序資料結構。
  • 目標 1：邏輯與物理分離。邏輯順序不應依賴於物理位置；元素應允許隨意存放於記憶體中的任何位置。
  • 目標 2：動態大小。結構必須能按需求即時擴大或縮小，無需定期進行昂貴的 $O(n)$ 重新配置。
  • 目標 3：常數時間局部修改。一旦找到插入點 $i$，修改序列只需常數個指標操作即可完成（$O(1)$）。
  • 此方法將複雜度從移動資料（移動元素）轉移到管理關係（指標）。

順序結構對比

操作陣列（目標）連結結構（目標）
隨機存取$O(1)$$O(n)$（需遍歷）
在 $i$ 處插入/刪除$O(n)$（移位）$O(1)$（指標更新，一旦找到 $i$ 即可）
記憶體配置連續非連續（動態）